package com.linyaonan.leetcode.medium._49;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *
 * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
 *
 * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
 *
 *
 *
 * 示例 1:
 *
 * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 * 示例 2:
 *
 * 输入: strs = [""]
 * 输出: [[""]]
 * 示例 3:
 *
 * 输入: strs = ["a"]
 * 输出: [["a"]]
 *
 *
 * 提示：
 *
 * 1 <= strs.length <= 10^4
 * 0 <= strs[i].length <= 100
 * strs[i] 仅包含小写字母
 *
 * @author: Lin
 * @date: 2024/9/18
 */
public class OverNumStr {

    /**
     * 思路：
     * 1. 首先将拿到额字符串子集进行排序，然后匹配是否已有匹配后字符串相等的集合
     * 2. 如果存在则进行加入，否则创建新的集合
     */

    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }
        // 用于存储排序后字符串以及原始字符串结果列表
        HashMap<String, List<String>> temp = new HashMap<>();
        // 用于返回
        ArrayList<List<String>> result = new ArrayList<>();
        for (String str : strs) {
            String sortStr = getSortStr(str);
            if (temp.containsKey(sortStr)) {
                temp.get(sortStr).add(str);
            } else {
                temp.put(sortStr, new ArrayList<>());
                temp.get(sortStr).add(str);
            }
        }
        for (Map.Entry<String, List<String>> entry : temp.entrySet()) {
            result.add(entry.getValue());
        }
        return result;
    }

    public String getSortStr(String str) {
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            for (int j = i + 1; j < chars.length; j++) {
                if (chars[i] > chars[j]) {
                    char temp = chars[i];
                    chars[i] = chars[j];
                    chars[j] = temp;
                }
            }
       }
        return new String(chars);
    }

}
